/**
 * Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path 
from the root node down to the nearest leaf node.
 */
package com.xinpan.exercise;

public class MinimumDepthofBinaryTree {
    public int minDepth(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null)
            return 0;
        
        int l = subDepth(root.left, 1);
        int r = subDepth(root.right, 1);
        if(l == 1)
            return r;
        else if(r == 1)
            return l;
        
        return Math.min(l, r);
    }
    
    public int subDepth(TreeNode root, int depth)
    {
        if(root == null)
            return depth;
        
        int l = subDepth(root.left, depth+1);
        int r = subDepth(root.right, depth+1);
        if(l == depth+1 && r != depth+1)
            return r;
        else if(l != depth+1 && r == depth+1)
            return l;
        else
            return Math.min(l, r);
    }
}
